package fr.kyvos.optimization;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.Random;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 * Class KspSolution
 * 
 * @file KspSolution.java
 * @author fr.kyvos
 * @date 01 January 2013
 *
 */

public class KspSolution extends SolutionBoolean {
	public static final int ROULETTE_BIAISEE_RANDOM = 0;
	public static final int ROULETTE_BIAISEE_EQUALS = 1;
	
	protected double mWeight;				// weight of the solution
	protected double mProfit;				// profit of the solution
	
	/**
	 * Constructor
	 * Build a solution with only false values
	 * 
	 * @param pSize of the solution
	 */
	public KspSolution(int pSize) {
		super(pSize);

		mWeight = 0.0;
		mProfit = 0.0;
	}
		
	/**
	 * Constructor
	 * Build a solution with random boolean values
	 * 
	 * @param pSize of the solution
	 * @param pRandomBoolean
	 */
	public KspSolution(int pSize, Random pRandomBoolean) {
		super(pSize,pRandomBoolean);

		mWeight = 0.0;
		mProfit = 0.0;
	}
		
	/**
	 * @return the weight of the solution
	 */
	public double getWeight() {
		return mWeight;
	}

	/**
	 * @param pWeight the weight to set
	 */
	public void setWeight(double pWeight) {
		mWeight = pWeight;
	}

	/**
	 * @return the profit of the solution
	 */
	public double getProfit() {
		return mProfit;
	}

	/**
	 * @param mProfit the profit to set
	 */
	public void setProfit(double pProfit) {
		mProfit = pProfit;
	}

	/**
	 * Copy pSolution in the current solution
	 * 
	 * @param pSolution
	 */
	public boolean copySolution(KspSolution pSolution) {
		if (pSolution.mSize == mSize) {
			mSize = pSolution.mSize;
			mNbTrue = pSolution.mNbTrue;
			mFitness = pSolution.mFitness;		
			for (int i=0;i<mSize;i++) {
				mValues.set(i,pSolution.getValueAtPosition(i));
			}
			mWeight = pSolution.mWeight;
			mProfit = pSolution.mProfit;
			return true;
		}
		else {
			return false;
		}
	}

	/**
     * Display the solution
     */
	@Override
	public String toString() {
		StringBuilder result = new StringBuilder();
	    String newLine = System.getProperty("line.separator");
	    Iterator<Boolean> lIt = mValues.iterator();
	    
		if (mNbTrue == 0) {
			result.append("Solution (null): [");
		}
		else {
			result.append("Solution ("+mFitness+"/"+mWeight+"): [");
		}
		while (lIt.hasNext()) {
			if (lIt.next().booleanValue()) { result.append(" 1"); }
			else { result.append(" 0"); }
		}
		result.append(" ]");
		result.append(newLine);
       	return result.toString();
    }
	
	public void addItem(int itemPosition, KspItem item) {
		this.setValueAtPosition(itemPosition, true);
		this.setWeight(this.getWeight()+item.getWeight());
		this.setProfit(this.getProfit()+item.getProfit());
		this.setNbTrue(this.getNbTrue()+1);
	}
	
	public void removeItem(int itemPosition, KspItem item) {
		this.setValueAtPosition(itemPosition, false);
		this.setWeight(this.getWeight()-item.getWeight());
		this.setProfit(this.getProfit()-item.getProfit());
		this.setNbTrue(this.getNbTrue()-1);
	}
	
	public ArrayList<KspSolution> Voisinnage(ArrayList<KspItem> mItemsList,double mCapacity) {
		
		int nbElements = mValues.size();
		
		ArrayList<KspSolution> mVoisin;
		KspSolution liste;
		mVoisin = new ArrayList<KspSolution>();
		
		for (int i=0;i<nbElements;i++) {
			
			liste = new KspSolution(nbElements);
			liste.copySolution(this);
			
			//System.out.println("pos" + i + " = "+liste.getValueAtPosition(i));
			
			//System.out.println("liste avant me set : "+liste.toString());
			if (liste.getValueAtPosition(i))
			{
				
				liste.setValueAtPosition(i, false);
				mVoisin.add(liste);
			}
			else
			{
				//System.out.println("depassement de capacite ? "+!((mItemsList.get(i).getWeight()+liste.getWeight())<mCapacity));
				//System.out.println((mItemsList.get(i).getWeight()+liste.getWeight())+" < "+mCapacity);
				
				//System.out.println(mItemsList.get(i).getWeight() + "toto : " + liste.getWeight() + "total :" +mCapacity );
				if ((mItemsList.get(i).getWeight()+liste.getWeight())<mCapacity)
				{
					liste.setValueAtPosition(i,true);
					mVoisin.add(liste);
				}
			}
			
			//System.out.println("liste apres me set : "+liste.toString());
			
			
		}
		/*
		/*
		System.out.println("LES VOISINS\n---------------");
		for (int i=0;i<mVoisin.size();i++)
		{
			System.out.println(mVoisin.get(i).toString());
		}
		System.out.println("---------------");
		*/
		
		return mVoisin;
			
		}
		
	public static ArrayList<KspSolution> init_first_population(int pop_size, int solution_size) throws SecurityException, IOException {
		return init_first_population(pop_size, solution_size, KnapSackProblem.getSimpleLogger("[log]_init_first_population"));
	}
	
		public static ArrayList<KspSolution> init_first_population(int pop_size, int solution_size, Logger logger) {
			//logger.log(Level.INFO, "---------------- Start of method 'init_first_population' ----------------");
			
			ArrayList<KspSolution> new_population = new ArrayList<KspSolution>(pop_size);
			
			KspSolution curr_solution;
			// on genere des solutions aleatoires
			for (int i=0; i<pop_size; i++) {
				curr_solution = new KspSolution(solution_size, new Random());
				
				//logger.log(Level.INFO, "nouvelle solution : \n"+curr_solution.toString());
				
				// TODO : question => dans la population initiale, est-ce qu'on peut avoir plusieurs
				// fois la meme solution ?
				new_population.add(curr_solution);
			}
			
			//logger.log(Level.INFO, "---------------- End of method 'init_first_population' ----------------");
			
			return new_population;
		}
		
		
		
		
		
		public static ArrayList<KspSolution> reproduce(
				ArrayList<KspSolution> population) throws Exception {
			ArrayList<KspSolution> lReproducted = new ArrayList<KspSolution>();

			Random rand = new Random();

			double[] cumFitness = new double[population.size()];

			cumFitness[0] = population.get(0).getFitness();

			// On cumule le fitness de toutes les solutions de la population
			for (int i = 1; i < population.size(); i++) {
				cumFitness[i] = cumFitness[i - 1]
						+ population.get(i).getFitness();
			}

			for (int i = 0; i < population.size(); i++) {
				// On tire un nombre aléatoire * le cumul total
				double rendTemp = rand.nextDouble()
						* cumFitness[cumFitness.length - 1];
				// On cherche l'indice correspondant à cette solution dans la
				// population
				int index = Arrays.binarySearch(cumFitness, rendTemp);

				if (index < 0) {
					index = Math.abs(index + 1);
				}
				// On ajoute la solution trouvée dans la nouvelle population
				lReproducted.add(population.get(index));
			}

			return lReproducted;
		}
		
		
		
		
		
		
		public static ArrayList<KspSolution> reproduction(ArrayList<KspSolution> population, int mode) throws SecurityException, IOException {
			return reproduction(population, mode, KnapSackProblem.getSimpleLogger("reproduction"));
		}
		
		/**
		 * We assume that each solution has its fitness already calculated.
		 * @param population
		 * @return
		 */
		public static ArrayList<KspSolution> reproduction(ArrayList<KspSolution> population, int mode, Logger logger) {
			//logger.log(Level.INFO, "---------------- Start of method 'reproduction' ----------------");
			
			int pop_size = population.size();
			//logger.log(Level.INFO,"population size : "+pop_size);
			ArrayList<KspSolution> new_population = new ArrayList<KspSolution>(pop_size);
			
			double[] fitness = new double[pop_size];
			double[] fitness_cumules = new double[pop_size];
			double sum_fitness = 0;
			
			String str_fitness = "[";
			String str_fitness_cumules = "[";
			
			int i;
			for (i=0; i<pop_size; i++) {
				fitness[i] = population.get(i).getFitness();
				str_fitness += fitness[i]+" , ";
				
				// array of cumulated fitnesses
				sum_fitness += fitness[i];
				fitness_cumules[i] = sum_fitness;
				str_fitness_cumules += fitness_cumules[i]+" , ";
			}
			
			str_fitness += "]";
			//logger.log(Level.INFO, "fitness[] : "+str_fitness);
			
			str_fitness_cumules += "]";
			//logger.log(Level.INFO, "fitness_cumules[] : "+str_fitness_cumules);
			
			// Nombre de tirages pour la roulette biaisee
			Random rand = new Random();
			double[] tirages_roulette;
			tirages_roulette = new double[pop_size];
			
			String str_tirages_roulette = "[";
			if (mode == ROULETTE_BIAISEE_RANDOM)
			{
				//logger.log(Level.INFO, "Le mode est ROULETTE_BIAISEE_RANDOM");
				
				
				// On tire n fois la roulette (aleatoire)
				for (int j =0; j<pop_size; j++) {
					tirages_roulette[j] = rand.nextDouble() * fitness_cumules[pop_size-1];
					str_tirages_roulette += tirages_roulette[j]+" , ";
				}
			}
			else if (mode == ROULETTE_BIAISEE_EQUALS) {
				//logger.log(Level.INFO, "Le mode est ROULETTE_BIAISEE_EQUALS");
				// On tire une fois et les autres tirages se repartissent a distance egale
				tirages_roulette[0] = rand.nextDouble() * fitness_cumules[pop_size-1];
				
				//logger.log(Level.INFO,"Le premier tirage est : "+tirages_roulette[0]);
				str_tirages_roulette += tirages_roulette[0]+" , ";
				
				double ecart_tirages = fitness_cumules[pop_size-1] / pop_size;
				//logger.log(Level.INFO, "ecart_tirages : "+ecart_tirages);
				
				double next_value_tirage = tirages_roulette[0];
				for(int j=1; j<pop_size; j++) {
					next_value_tirage += ecart_tirages;
					
					//logger.log(Level.INFO, "next_value_tirage : "+next_value_tirage);
					
					if(next_value_tirage > fitness_cumules[pop_size-1]) {
						// si on depasse le meilleur fitness cumule, on revien au debut (comme
						// dans un cercle)
						//logger.log(Level.INFO, next_value_tirage+" depasse le meilleur fitness cumule ("+fitness_cumules[pop_size-1]+")");
						next_value_tirage -= fitness_cumules[pop_size-1]; 
						//logger.log(Level.INFO, "next_value_tirage (modifiee) : "+next_value_tirage);
					}
					
					tirages_roulette[j] = next_value_tirage;
					str_tirages_roulette += tirages_roulette[j]+" , ";
				}
			}
			str_tirages_roulette += "]";
			
			logger.log(Level.INFO, "tirages_roulette[] : "+str_tirages_roulette);
			
			// on realise les tirages
			for (i=0; i<pop_size; i++) {
				int index_of_solution = Arrays.binarySearch(fitness_cumules, tirages_roulette[i]);
				//logger.log(Level.INFO, "index_of_solution (from Arrays.binarySearch) : "+index_of_solution+ " (tirages_roulette : "+tirages_roulette[i]+")");
				
				// transformation a cause de ce que nous renvoie Arrays.binarySearch
				/*
				if (index_of_solution < 0) {
					index_of_solution = (index_of_solution * -1) - 1 ;
					//logger.log(Level.INFO, "index_of_solution (apres transformation) : "+index_of_solution);
				}
				*/
				//System.out.println("index_of_solution : "+index_of_solution);
				index_of_solution = Math.abs(index_of_solution+1);
				
				/*
				double[] test_fit = new double[]{0.0 , 2781.0 , 2271.0 , 2491.0 , 2416.0 , 0.0 , 2810.0 , 0.0 , 2929 , 0.0};
				double[] test =     new double[]{0.0 , 2781.0 , 5052.0 , 7543.0 , 9959.0 , 9959.0 , 12769.0 , 12769.0 , 15698.0 , 15698.0};
				index_of_solution = Arrays.binarySearch(test, 12769.0);
				
				System.out.println("fitness["+index_of_solution+"] : "+fitness[index_of_solution]);
				*/
				
				// Si la solution choisie a un fitness de zero, ca ne va pas (elle ne devrait pas
				// etre choisie) => on cherche a gauche de la solution la premiere solution qui
				// a un fitness non nul (elle devrait normalement avoir le meme fitness cumule)
				if (fitness[index_of_solution] == 0)
				{
					double value_searched = fitness_cumules[index_of_solution];
					//System.out.println("fitness_cumules[index_of_solution] : "+fitness_cumules[index_of_solution]);
					for (int k=index_of_solution; k>0; k--) {
						//System.out.println("k : "+k+" | fitness[k] : "+fitness[k]+" | fitness_cumules[k] : "+fitness_cumules[k]);
						if (fitness[k] > 0 && fitness_cumules[k] == value_searched)
							index_of_solution = k;
					}
					//logger.log(Level.INFO, "Nouvel index of solution  : "+index_of_solution);
				}
				
				//logger.log(Level.INFO, "TEST BinarySearch : "+index_of_solution);
				
				KspSolution solution_choisie = population.get(index_of_solution);
				//logger.log(Level.INFO, "solution choisie : "+solution_choisie);
				
				new_population.add(solution_choisie);
			}
			
			//logger.log(Level.INFO, "---------------- End of method 'reproduction' ----------------");
			
			return new_population;
		}
	
		@Override
		public boolean equals(Object obj) {
			// TODO Auto-generated method stub
			if (!(obj instanceof KspSolution))
				return false;
			
			KspSolution other_solution = (KspSolution) obj;
			
			if (mValues.size() != other_solution.mValues.size())
				return false;
			
			boolean same_elements = true;
			for (int i=0; i<mValues.size() && same_elements; i++) {
				if (!mValues.get(i).equals(other_solution.mValues.get(i)))
					same_elements = false;
			}
			
			return same_elements;
		}
		
		public static ArrayList<KspSolution> mutation (ArrayList<KspSolution> pop, double proba) {
			
			int nbElement = pop.get(0).getSize();
			double tirageAleatoire;
			boolean valeur;

			Random rand = new Random();
			
			for (int i=0;i<pop.size();i++)
			{
				boolean amute = false;
				//System.out.println("avant mutation : "+pop.get(i));
				for (int y=0;y<nbElement;y++)
				{
					tirageAleatoire = rand.nextDouble();
					
					if (tirageAleatoire<proba)
					{
						amute = true;
						
						valeur = pop.get(i).getValueAtPosition(y);
						if (valeur)
						{
							pop.get(i).setValueAtPosition(y, false);
						}
						else
						{
							pop.get(i).setValueAtPosition(y, true);
						}
					}
				}
				/*
				if (amute)
					System.out.println("apres mutation : "+pop.get(i));
					*/
			}
			
			return pop;
			
		}
		
		public static ArrayList<KspSolution> croisement(ArrayList<KspSolution> pop) {
			
			int nbElement,posCroisement;
			int i =0;
			int coteCroisement;
			
			nbElement = pop.get(0).getSize();
			
			Random rand = new Random();
			
		    Collections.shuffle(pop);
		   
			
			while (i<pop.size())
			{
				posCroisement = rand.nextInt(nbElement);
				
				/*
				System.out.println("croisement"+posCroisement);
				System.out.println("toto"+pop.get(i));
				System.out.println("tata"+pop.get(i+1));
				***/
				
				coteCroisement = rand.nextInt(2);
				
				if (coteCroisement==1)
				{
				
				for (int y=posCroisement+1;y<nbElement;y++)
				{
					
						KspSolution solution_temp = new KspSolution(nbElement);
						solution_temp.copySolution(pop.get(i+1));
						
						pop.get(i+1).setValueAtPosition(y, pop.get(i).getValueAtPosition(y));
						
						pop.get(i).setValueAtPosition(y, solution_temp.getValueAtPosition(y));
				}
				}
				else
				{
					for (int y=posCroisement-1;y>=0;y--)
					{
						
							KspSolution solution_temp = new KspSolution(nbElement);
							solution_temp.copySolution(pop.get(i+1));
							
							pop.get(i+1).setValueAtPosition(y, pop.get(i).getValueAtPosition(y));
							
							pop.get(i).setValueAtPosition(y, solution_temp.getValueAtPosition(y));
					}
				}
				/*
				for (int y=posCroisement-1;y>=0;y--)
				{	
					pop.get(i).setValueAtPosition(y, pop.get(i+1).getValueAtPosition(y));
				}
				*/
				/*
				System.out.println("pouet"+pop.get(i));
				System.out.println("popo"+pop.get(i+1));
				*/
				
				i=i+2;
			}
			
			return pop;
		}
		
		
}
